package com.atguigu.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author 龍
 * 冒泡排序：相邻的元素之间进行排序。
 * (1) 一共进行 数组的大小-1 次 大的循环
 * (2)每一趟排序的次数在逐渐的减少
 * (3) 如果我们发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。这个就是优化
 * 时间复杂度是：n^2
 * 80000个数据的排序时间为15s左右
 */
public class MaoPaoSort {
    public static void main(String[] args) {
        int[] arrays = new int[]{3, 9, -1, 10, 20};
        System.out.print("原始数组：");
        System.out.println(Arrays.toString(arrays));
        bubbleSort(arrays);
        System.out.print("进行排序之后的数组：");
        System.out.println(Arrays.toString(arrays));
        System.out.println("===============================");
        int[] arr=new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=new Random().nextInt(8000000);
        }
        //System.out.println(Arrays.toString(arr));
        System.out.println("排序前的时间："+System.currentTimeMillis());
        bubbleSort(arr);
        System.out.println("排序后的时间："+System.currentTimeMillis());
        //System.out.println(Arrays.toString(arr));

    }

    /**
     * 冒泡排序法
     * @param :需要排序的数组
     */
    public static void bubbleSort(int[] arr){
        /*
            temp:是一个临时变量。
            count:用来计数总共进行了几轮
            flag:标志位，表明某轮是否进行了交换。
         */
        int temp=0;
        int count=0;
        boolean flag=false;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length-1; j++) {
                if (arr[j] > arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag=true;
                }
            }
            // 此处进行了优化，如果某一轮没有发生交换，则表明已经排好了顺序，不需要再次进行交换。
            if (!flag){
                //表明本次没有发生交换。
                break;
            }else{
                flag=false;
            }
            count++;
        }
        System.out.println("count:"+count);
    }

}
